﻿// 最短路计数.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。

/*
* https://loj.ac/p/10077
【题目描述】
给出一个 N 个顶点 M 条边的无向无权图，顶点编号为 1∼N。问从顶点 1 开始，到其他每个点的最短路有几条。

输入格式
第一行包含 2 个正整数 N,M，为图的顶点数与边数。
接下来 M行，每行两个正整数 x,y，表示有一条顶点 x 连向顶点 y 的边，请注意可能有自环与重边。


【输出】
输出 N 行，每行一个非负整数，第 i 行输出从顶点 1 到顶点 i 有多少条不同的最短路，由于答案有可能会很大，
你只需要输出mod 100003后的结果即可。如果无法到达顶点 i 则输出 0。

【输入样例】
5 7
1 2
1 3
4 5
4 5
2 4
3 4
2 3

【输出样例】
1
1
1
2
4
【提示】
样例解释

1 到 5 的最短路有 4 条，分别为 2 条 1→2→4→5 和 2 条 1→3→4→5（由于 4→5 的边有 2 条）。

数据范围：

对于 20% 的数据，N≤100；

对于 60% 的数据，N≤1000；

对于 100% 的数据，1≤N≤100000,0≤M≤200000。
*/


#include <iostream>
#include <queue>
#include <vector>
#include <cstring>

using  namespace std;


typedef pair<int, int> PII;

const int N = 100010, M = 400010;
const int MOD = 100003;
int h[N], e[M], ne[M], w[M], idx;
int cnt[N], dist[N];
bool st[N];
int n, m;


void add(int a, int b, int l) {
	e[idx] = b, w[idx] = l, ne[idx] = h[a], h[a] = idx++;
}

void dijkstra() {
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0; cnt[1] = 1;
	priority_queue<PII, vector<PII>, greater<PII>> heap;
	heap.push({ 0, 1 });      // first存储距离，second存储节点编号
	while (heap.size()) {
		auto t = heap.top();
		heap.pop();

		int ver = t.second, distance = t.first;
		if (st[ver]) continue;
		st[ver] = true;

		for (int i = h[ver]; i != -1; i = ne[i])
		{
			int j = e[i];
			if (dist[j] > distance + w[i])
			{
				dist[j] = distance + w[i];
				cnt[j] = cnt[ver]; cnt[j] %= MOD;
				heap.push({ dist[j], j });
			}
			else if (dist[j] == distance + w[i]) {
				cnt[j] += cnt[ver]; cnt[j] %= MOD;
				//heap.push({ dist[j], j });
			}
		}
	}
}



int main()
{
	memset(h, -1, sizeof h);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b; cin >> a >> b;
		add(a, b, 1); add(b, a, 1);
	}
	
	dijkstra();

	for (int i = 1; i <= n; i++) {
		cout << cnt[i] << endl;
	}

	return 0;
}

 
